home *** CD-ROM | disk | FTP | other *** search
/ Linux Cubed Series 8: LINUX Games / Linux Cubed Series 8 - LINUX Games.iso / games / muds / lpmud312.tar / lpmud312 / smalloc.c < prev    next >
C/C++ Source or Header  |  1991-10-31  |  12KB  |  531 lines
  1. /* Satoria's malloc intended to be optimized for lpmud.
  2. ** this memory manager distinguishes between two sizes
  3. ** of blocks: small and large.  It manages them separately
  4. ** in the hopes of avoiding fragmentation between them.
  5. ** It expects small blocks to mostly be temporaries.
  6. ** It expects an equal number of future requests as small
  7. ** block deallocations.
  8. */
  9. #include <stdio.h>
  10. #include <memory.h>
  11. #include "lint.h"
  12.  
  13. #ifdef MSDOS
  14. #define char void
  15. #endif
  16.  
  17. #define fake(s)
  18. #define smalloc malloc
  19. #define sfree free
  20. #define srealloc realloc
  21.  
  22. #define SMALL_BLOCK_MAX_BYTES    32
  23. #define SMALL_CHUNK_SIZE    0x4000
  24. #define CHUNK_SIZE        0x40000
  25.  
  26. #define SINT sizeof(int)
  27. #define SMALL_BLOCK_MAX (SMALL_BLOCK_MAX_BYTES/SINT)
  28.  
  29. #define PREV_BLOCK    0x80000000
  30. #define THIS_BLOCK    0x40000000
  31. #define MASK        0x0FFFFFFF
  32.  
  33. #define MAGIC        0x17952932
  34.  
  35. /* SMALL BLOCK info */
  36.  
  37. typedef unsigned int u;
  38.  
  39. static u *sfltable[SMALL_BLOCK_MAX];    /* freed list */
  40. static u *next_unused;
  41. static u unused_size;            /* until we need a new chunk */
  42.  
  43. /* LARGE BLOCK info */
  44.  
  45. static u *free_list;
  46. static u *start_next_block;
  47.  
  48. /* STATISTICS */
  49.  
  50. static int small_count[SMALL_BLOCK_MAX];
  51. static int small_total[SMALL_BLOCK_MAX];
  52. static int small_max[SMALL_BLOCK_MAX];
  53. static int small_free[SMALL_BLOCK_MAX];
  54.  
  55. typedef struct { unsigned counter, size; } stat;
  56. #define count(a,b) { a.size+=(b); if ((b)<0) --a.counter; else ++a.counter; }
  57.  
  58. int debugmalloc;    /* Only used when debuging malloc() */
  59.  
  60. /********************************************************/
  61. /*  SMALL BLOCK HANDLER                    */
  62. /********************************************************/
  63.  
  64. static char *large_malloc();
  65. static void large_free();
  66.  
  67. #define s_size_ptr(p)    (p)
  68. #define s_next_ptr(p)    ((u **) (p+1))
  69.  
  70. stat small_alloc_stat;
  71. stat small_free_stat;
  72. stat small_chunk_stat;
  73.  
  74. char *smalloc(size)
  75.   u size;
  76. {
  77.   int i;
  78.   u *temp;
  79.  
  80.   if (size == 0)
  81.       fatal("Malloc size 0.\n");
  82.   if (size>SMALL_BLOCK_MAX_BYTES)
  83.     return large_malloc(size,0);
  84.  
  85.   i = (size - 1) >> 2;
  86.   size = i+2;                /* block size in ints */
  87.   count(small_alloc_stat,size << 2);
  88.  
  89.   small_count[i] += 1;            /* update statistics */
  90.   small_total[i] += 1;
  91.   if (small_count[i] >= small_max[i])
  92.     small_max[i] = small_count[i];
  93.  
  94.   if (sfltable[i]) 
  95.     {                    /* allocate from the free list */
  96.       count(small_free_stat, -(int) (size << 2));
  97.       temp = sfltable[i];
  98.       sfltable[i] = * (u **) (temp+1);
  99. fake("From free list.");
  100.       return (char *) (temp+1);
  101.     }                    /* else allocate from the chunk */
  102.  
  103.   if (unused_size<size)            /* no room in chunk, get another */
  104.     {
  105.       fake("Allocating new small chunk.");
  106.       next_unused = (u *) large_malloc(SMALL_CHUNK_SIZE,1);
  107.       if (next_unused == 0)
  108.     return 0;
  109.       count(small_chunk_stat, SMALL_CHUNK_SIZE+SINT);
  110.       unused_size = SMALL_CHUNK_SIZE / SINT;
  111.     }
  112. else fake("Allocated from chunk.");
  113.  
  114.  
  115.   temp = (u *) s_next_ptr(next_unused); 
  116.  
  117.   *s_size_ptr(next_unused) = size;
  118.   next_unused += size;
  119.   unused_size -= size;
  120.  
  121.   return (char *) temp;
  122. }
  123.  
  124. char *debug_free_ptr;
  125.  
  126. void sfree(ptr)
  127. char *ptr;
  128. {
  129.   u *block;
  130.   u i;
  131.  
  132.   debug_free_ptr = ptr;
  133.   block = (u *) ptr;
  134.   block -= 1;
  135.   if ((*s_size_ptr(block) & MASK) > SMALL_BLOCK_MAX + 1)
  136.     { large_free(ptr); return; }
  137.  
  138.   i = *block - 2;
  139.   count(small_alloc_stat, - (int) ((i+2) << 2));
  140.   count(small_free_stat, (i+2) << 2);
  141.   *s_next_ptr(block) = sfltable[i];
  142.   sfltable[i] = block;
  143.   small_free[i] += 1;
  144. fake("Freed");
  145. }
  146.  
  147. /************************************************/
  148. /*    LARGE BLOCK HANDLER            */
  149. /************************************************/
  150.  
  151. #define BEST_FIT    0
  152. #define FIRST_FIT    1
  153. #define HYBRID        2
  154. int fit_style =BEST_FIT;
  155.  
  156. #define l_size_ptr(p)        (p)
  157. #define l_next_ptr(p)        (*((u **) (p+1)))
  158. #define l_prev_ptr(p)        (*((u **) (p+2)))
  159. #define l_next_block(p)        (p + (*(p)))
  160. #define l_prev_block(p)     (p - (*(p-1)))
  161. #define l_prev_free(p)        (!(*p & PREV_BLOCK))
  162. #define l_next_free(p)        (!(*l_next_block(p) & THIS_BLOCK))
  163.  
  164. void show_block(ptr)
  165. u *ptr;
  166. {
  167.   printf("[%c%d: %d]  ",(*ptr & THIS_BLOCK ? '+' : '-'),
  168.         (int) ptr, *ptr & MASK);
  169. }
  170.  
  171. void show_free_list()
  172. {
  173.    u *p;
  174.    p = free_list;
  175.    while (p) {
  176.      show_block(p);
  177.      p = l_next_ptr(p);
  178.    }
  179.    printf("\n");
  180. }
  181.  
  182. stat large_free_stat;     
  183. void remove_from_free_list(ptr)
  184. u *ptr;
  185. {
  186.    count(large_free_stat, - (int) (*ptr & MASK) << 2);
  187.  
  188.    if (l_prev_ptr(ptr))
  189.      l_next_ptr(l_prev_ptr(ptr)) = l_next_ptr(ptr);
  190.    else
  191.      free_list = l_next_ptr(ptr);
  192.  
  193.    if (l_next_ptr(ptr))
  194.      l_prev_ptr(l_next_ptr(ptr)) = l_prev_ptr(ptr);
  195. }
  196.  
  197. void add_to_free_list(ptr)
  198. u *ptr;
  199. {
  200.   extern int puts();
  201.   count(large_free_stat, (*ptr & MASK) << 2);
  202.  
  203.   if (free_list && l_prev_ptr(free_list)) 
  204.     puts("Free list consistency error.");
  205.  
  206.   l_next_ptr(ptr) = free_list;
  207.   if (free_list) 
  208.     l_prev_ptr(free_list) = ptr;
  209.   l_prev_ptr(ptr) = 0;
  210.   free_list = ptr;
  211. }
  212.  
  213. void build_block(ptr, size)    /* build a properly annotated unalloc block */
  214. u *ptr;
  215. u size;
  216. {
  217.   *(ptr) = (*ptr & PREV_BLOCK) | size;        /* mark this block as free */
  218.   *(ptr+size-1) = size;
  219.   *(ptr+size) &= (MASK | THIS_BLOCK); /* unmark previous block */
  220. }
  221.  
  222. static void mark_block(ptr)        /* mark this block as allocated */
  223. u *ptr;
  224. {
  225.   *l_next_block(ptr) |= PREV_BLOCK;
  226.   *ptr |= THIS_BLOCK;
  227. }
  228.  
  229. /*
  230.  * It is system dependent how sbrk() aligns data, so we simpy use brk()
  231.  * to insure that we have enough.
  232.  */
  233. stat sbrk_stat;
  234. static char *esbrk(size)
  235. u size;
  236. {
  237.   extern char *sbrk();
  238.   extern int brk();
  239.   static char *current_break;
  240.  
  241.   if (current_break == 0)
  242.     current_break = sbrk(0);
  243.   if (brk(current_break + size) == -1)
  244.     return 0;
  245.   count(sbrk_stat,size);
  246.   current_break += size;
  247.   return current_break - size;
  248. }
  249.  
  250. stat large_alloc_stat;
  251. static char *large_malloc(size, force_more)
  252. u size;
  253. int force_more;
  254. {
  255.   u best_size, real_size;
  256.   u *first, *best, *ptr;
  257.  
  258.   size = (size + 7) >> 2;         /* plus overhead */
  259.   count(large_alloc_stat, size << 2);
  260.   first = best = 0;
  261.   best_size = MASK;
  262.  
  263.   if (force_more)
  264.     ptr = 0;
  265.   else
  266.     ptr = free_list;
  267.  
  268.   while (ptr) {
  269.     u tempsize;
  270.         /* Perfect fit? */
  271.     tempsize = *ptr & MASK;
  272.     if (tempsize == size) {
  273.       best = first = ptr;
  274.       break;        /* always accept perfect fit */
  275.     }
  276.  
  277.         /* does it really even fit at all */
  278.     if (tempsize >= size + SMALL_BLOCK_MAX + 1)
  279.       {
  280.         /* try first fit */
  281.         if (!first) 
  282.       {
  283.         first = ptr;
  284.         if (fit_style == FIRST_FIT)
  285.             break;            /* just use this one! */
  286.       }
  287.         /* try best fit */
  288.     tempsize -= size;
  289.     if (tempsize>0 && tempsize<=best_size) 
  290.       {
  291.         best = ptr;
  292.         best_size = tempsize;
  293.           }
  294.       }
  295.     ptr = l_next_ptr(ptr);
  296.   } /* end while */
  297.  
  298.   if (fit_style==BEST_FIT) ptr = best;
  299.   else ptr = first;    /* FIRST_FIT and HYBRID both leave it in first */
  300.  
  301.   if (!ptr)        /* no match, allocate more memory */
  302.     {
  303.       u chunk_size, block_size;
  304.       block_size = size*SINT;
  305.       if (force_more || (block_size>CHUNK_SIZE))
  306.     chunk_size = block_size;
  307.       else
  308.     chunk_size = CHUNK_SIZE;
  309.  
  310.       if (!start_next_block) {
  311.     start_next_block = (u *) esbrk(SINT);
  312.     if (!start_next_block)
  313.       return 0;
  314.     *(start_next_block) = PREV_BLOCK;
  315. fake("Allocated little fake block");
  316.       }
  317.  
  318.       ptr = (u *) esbrk(chunk_size);
  319.       if (ptr == 0)
  320.       return 0;
  321.       ptr -= 1;        /* overlap old memory block */
  322.       block_size = chunk_size / SINT;
  323.  
  324.                   /* configure header info on chunk */
  325.       
  326.       build_block(ptr,block_size);
  327. if (force_more)
  328. fake("Build little block");
  329. else
  330. fake("Built memory block description.");
  331.       *l_next_block(ptr)=THIS_BLOCK;
  332.       add_to_free_list(ptr);
  333.     }    /* end of creating a new chunk */
  334.   remove_from_free_list(ptr);
  335.   real_size = *ptr & MASK;
  336.  
  337.   if (real_size != size) {
  338.     /* split block pointed to by ptr into two blocks */
  339.     build_block(ptr+size, real_size-size);
  340. fake("Built empty block");
  341.     add_to_free_list(ptr+size);
  342.     build_block(ptr, size);
  343.   }
  344.  
  345.   mark_block(ptr);
  346. fake("built allocated block");
  347.   return (char *) (ptr + 1);
  348. }
  349.  
  350. static void large_free(ptr)
  351. char *ptr;
  352. {
  353.   u size, *p;
  354.   p = (u *) ptr;
  355.   p-=1;
  356.   size = *p & MASK;
  357.   count(large_alloc_stat, - (int) (size << 2));
  358.  
  359.   if (l_next_free(p)) {
  360.     remove_from_free_list(l_next_block(p));
  361.     size += (*l_next_block(p) & MASK);
  362.     *p = (*p & PREV_BLOCK) | size;
  363.   }
  364.  
  365.   if (l_prev_free(p)) {
  366.     remove_from_free_list(l_prev_block(p));
  367.     size += (*l_prev_block(p) & MASK);
  368.     p = l_prev_block(p);
  369.   }
  370.  
  371.   build_block(p, size);
  372.  
  373.   add_to_free_list(p);
  374. }
  375.  
  376. char *srealloc(p, size)
  377. char *p; unsigned size;
  378. {
  379.    unsigned *q, old_size;
  380.    char *t;
  381.    
  382.    q = (unsigned *) p;
  383.    --q;
  384.    old_size = ((*q & MASK)-1)*sizeof(int);
  385.    if (old_size >= size)
  386.       return p;
  387.  
  388.    t = malloc(size);
  389.    if (t == 0) return (char *) 0;
  390.  
  391.    memcpy(t, p, old_size);
  392.    free(p);
  393.    return t;
  394. }
  395.  
  396.  
  397.  
  398. int resort_free_list() { return 0; }
  399. #define dump_stat(str,stat) add_message(str,stat.counter,stat.size)
  400. void dump_malloc_data()
  401. {
  402.   add_message("Type                   Count      Space (bytes)\n");
  403.   dump_stat("sbrk requests:     %8d        %10d (a)\n",sbrk_stat);
  404.   dump_stat("large blocks:      %8d        %10d (b)\n",large_alloc_stat);
  405.   dump_stat("large free blocks: %8d        %10d (c)\n\n",large_free_stat);
  406.   dump_stat("small chunks:      %8d        %10d (d)\n",small_chunk_stat);
  407.   dump_stat("small blocks:      %8d        %10d (e)\n",small_alloc_stat);
  408.   dump_stat("small free blocks: %8d        %10d (f)\n",small_free_stat);
  409.   add_message(
  410. "unused from current chunk          %10d (g)\n\n",unused_size<<2);
  411.   add_message(
  412. "    Small blocks are stored in small chunks, which are allocated as\n");
  413.   add_message(
  414. "large blocks.  Therefore, the total large blocks allocated (b) plus\n");
  415.   add_message(
  416. "the large free blocks (c) should equal total storage from sbrk (a).\n");
  417.   add_message(
  418. "Similarly, (e) + (f) + (g) equals (d).  The total amount of storage\n");
  419.   add_message(
  420. "wasted is (c) + (f) + (g); the amount allocated is (b) - (f) - (g).\n");
  421. }
  422.  
  423. /*
  424.  * calloc() is provided because some stdio packages uses it.
  425.  */
  426. char *calloc(nelem, sizel)
  427. #ifndef MSDOS
  428.     int nelem, sizel;
  429. #else
  430.     unsigned nelem, sizel;
  431. #endif
  432. {
  433.     char *p;
  434.  
  435.     if (nelem == 0 || sizel == 0)
  436.     return 0;
  437.     p = malloc(nelem * sizel);
  438.     if (p == 0)
  439.     return 0;
  440.     (void)memset(p, '\0', nelem * sizel);
  441.     return p;
  442. }
  443.  
  444. /*
  445.  * Functions below can be used to debug malloc.
  446.  */
  447.  
  448. #if 0
  449.  
  450. int debugmalloc;
  451. /*
  452.  * Verify that the free list is correct. The upper limit compared to
  453.  * is very machine dependant.
  454.  */
  455. verify_sfltable() {
  456.     u *p;
  457.     int i, j;
  458.     extern int end;
  459.  
  460.     if (!debugmalloc)
  461.     return;
  462.     if (unused_size > SMALL_CHUNK_SIZE / SINT)
  463.     apa();
  464.     for (i=0; i < SMALL_BLOCK_MAX; i++) {
  465.     for (j=0, p = sfltable[i]; p; p = * (u **) (p + 1), j++) {
  466.         if (p < (u *)&end || p > (u *) 0xfffff)
  467.         apa();
  468.         if (*p - 2 != i)
  469.         apa();
  470.     }
  471.     if (p >= next_unused && p < next_unused + unused_size)
  472.         apa();
  473.     }
  474.     p = free_list;
  475.     while (p) {
  476.     if (p >= next_unused && p < next_unused + unused_size)
  477.         apa();
  478.     p = l_next_ptr(p);
  479.     }
  480. }
  481.  
  482. verify_free(ptr)
  483.     u *ptr;
  484. {
  485.     u *p;
  486.     int i, j;
  487.  
  488.     if (!debugmalloc)
  489.     return;
  490.     for (i=0; i < SMALL_BLOCK_MAX; i++) {
  491.     for (j=0, p = sfltable[i]; p; p = * (u **) (p + 1), j++) {
  492.         if (*p - 2 != i)
  493.         apa();
  494.         if (ptr >= p && ptr < p + *p)
  495.         apa();
  496.         if (p >= ptr && p < ptr + *ptr)
  497.         apa();
  498.         if (p >= next_unused && p < next_unused + unused_size)
  499.         apa();
  500.     }
  501.     }
  502.  
  503.     p = free_list;
  504.     while (p) {
  505.     if (ptr >= p && ptr < p + (*p & MASK))
  506.         apa();
  507.     if (p >= ptr && p < ptr + (*ptr & MASK))
  508.         apa();
  509.     if (p >= next_unused && p < next_unused + unused_size)
  510.         apa();
  511.     p = l_next_ptr(p);
  512.     }
  513.     if (ptr >= next_unused && ptr < next_unused + unused_size)
  514.     apa();
  515. }
  516.  
  517. apa() {
  518.     int i;
  519.     i/0;
  520. }
  521.  
  522. static char *ref;
  523. test_malloc(p)
  524.     char *p;
  525. {
  526.     if (p == ref)
  527.     printf("Found 0x%x\n", p);
  528. }
  529.  
  530. #endif /* 0 (never) */
  531.